import java.util.Scanner;

/**
 * <p>
 * 希尔排序（缩小增量排序）
 * </p>
 * <p>
 * 插入排序的一种优化，死板的那套解释大家看课本吧，笔者个人不喜欢课本那种古板生硬的教学
 * </p>
 * <p>
 * 其实优化思路总的来说就是分组来“减少移动次数”，大家可以在代码中自行体会
 * </p>
 * <p>时间复杂度：O(N^2)（别问为什么，涉及数学证明笔者也不会...）</p>
 *
 * @author 没天赋
 * @since 2025-04-01
 */
public class shellSort {
    public static void main(String[] args) {
        final int N = 105;
        int[] a = new int[N];
        int n;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        // 输入数据
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }
        // 希尔排序的缩小增量就是 n/2，n/4，n/8...
        for (int d = n / 2; d > 0; d /= 2) {
            // 每组的第一个不需要排，所以从 d+1（每组第二个）开始
            for (int i = d + 1; i <= n; i++) {
                // 正常的插入排序算法
                int temp = a[i], j;
                for (j = i - d; j >= 1; j -= d) {
                    if (a[j] > temp) {
                        a[j + d] = a[j];
                    } else {
                        break;
                    }
                }
                a[j + d] = temp;
            }
            // 为了大家学习方便，每轮排序后都输出一次
            System.out.print("d = " + d + " : ");
            for (int i = 1; i <= n; i++) {
                System.out.print(a[i] + " ");
            }
            System.out.println();
        }
    }
}
/*
  排序算法的数据都比较容易构造，大家可以自行构造一些数据进行测试
  测试数据：
  5
  3 4 1 9 2
  --------------
  d = 2 : 1 4 2 9 3
  d = 1 : 1 2 3 4 9
 */